Tiered Sampling: An Efficient Method for Approximate Counting Sparse Motifs in Massive Graph Streams

摘要

We introduce Tiered Sampling, a novel technique for approximate countingsparse motifs in massive graphs whose edges are observed in a stream. Ourtechnique requires only a single pass on the data and uses a memory of fixedsize $M$, which can be magnitudes smaller than the number of edges. Our methods addresses the challenging task of counting sparse motifs -sub-graph patterns that have low probability to appear in a sample of $M$ edgesin the graph, which is the maximum amount of data available to the algorithmsin each step. To obtain an unbiased and low variance estimate of the count wepartition the available memory to tiers (layers) of reservoir samples. Whilethe base layer is a standard reservoir sample of edges, other layers arereservoir samples of sub-structures of the desired motif. By storing morefrequent sub-structures of the motif, we increase the probability of detectingan occurrence of the sparse motif we are counting, thus decreasing the varianceand error of the estimate. We demonstrate the advantage of our method in the specific applications ofcounting sparse 4 and 5-cliques in massive graphs. We present a completeanalytical analysis and extensive experimental results using both synthetic andreal-world data. Our results demonstrate the advantage of our method inobtaining high-quality approximations for the number of 4 and 5-cliques forlarge graphs using a very limited amount of memory, significantly outperformingthe single edge sample approach for counting sparse motifs in large scalegraphs.